Week 08: Local Optimization & Global Optimization

Local Optimization

Introduction

A language between the source and the target
- More details than the source
- Fewer details than the target
Intermediate language = high-level assembly
- Uses register names, but has an unlimited number
- Uses control structures like assembly language
- Uses opcodes but some are at higher level

Instruction

Each instruction is of the form
- x = y op z
- x = op y
- y and z are registers or constants
The expression x + y * z is translated
- t1 = y * z
- t2 = x + t1
Each subexpression has a name

Introduction

Most complexity in modern compilers is in the optimizer
- Also by far the largest phase
When should we perform optimizations?
- On AST
  - Pro: Machine Independent
  - Con: Too high level
- On assembly language
  - Pro: Exposes optimization opportunities
  - Con: Machine dependent
  - Con: Must reimplement optimizations when retargetting
- On an intermediate language
  - Pro: Machine independent
  - Pro: Exposes optimization opportunities

Optimization in block

A basic block is a maximal sequence of instructions with:
- no labels (except at the first instruction), and
- no jumps (except in the last instruction)
Idea:
- Cannot jump into a basic block (except at beginning)
- Cannot jump out of a basic block (except at end)
- A basic block is a single-entry, single-exit, straight-line code segment

Control-flow Graph

A control-flow graph is a directed graph with
- Basic blocks as nodes
- An edge from block A to block B if the execution can pass from the last instruction in A to the first instruction in B
  - E.g., the last instruction in A is jump to B
  - E.g., execution can fall-through from block A to block B

Remarks

Optimization seeks to improve a program's resource utilization
- Execution Time
- Code Size
- Network messages sent, etc.
Optimization should not alter what the program computes.

Optimization

Introduction

Optimize one basic block
Some statements can be deleted
- x = x + 0
- x = x * 1
Rewrite code in single assignment form.
- Each register occurs only once on the left-hand side of an assignment.
Constant Folding: c_1 op c_2
- Operation on constants can be computed at compile time
- It can be dangerous. Cross-compiling on different archs differs from on the same arch.
Eliminate unreachable basic blocks from the initial block
Common Subexpression Elimination
- x = y + z; w = y + z; => x = y + z; w = x;
- If w = x appears, replace all w with x.
Dead Code Elimination
- If w = xxxx;, then w does not appear anywhere else.
Performing one optimization enables another
- Optimizing compilers repeat optimizations until no improvement is possible
- The optimizer can also be stopped at any point to limit compilation time

Optimizations can be directly applied to assembly code
Peephole optimization replaces the sequence with another equivalent one (but faster)
Example
- move $a $b; move b a; => move $a $b;
- addiu $a $a i; addiu $a $a j; => addiu $a $a i+j;
- addiu $a $b 0; => move $a $b;
- move $a $a; => ;

Introduction

Use optimizations on an entire control-flow graph.
To replace a use of x by a constant k we must know:
- On every path to the use of x, the last assignment to x is x = k
- All paths includes paths around loops and through branches of conditionals
Checking the condition requires global dataflow analysis

Introduction

To replace a use of x by a constant k we must know:
- On every path to the use of x, the last assignment to x is x := k **
Global constant propagation can be performed at any point where ** holds
Consider the case of computing ** for a single variable X at all program points
To make the problem precise, we associate one of the following values with X at every program point
- $\perp$: This statement never executes.
- c: X = constant c
- T; X is not a constant.

Transfer function

The analysis of a complicated program can be expressed as a combination of simple rules relating the change in information between adjacent statements.
For each statement s, we compute information about the value of x immediately before and after s
- C(s, x, in) = value of x before s
- C(s, x, out) = value of x after s
Define a transfer function that transfers information one statement to another
- In the following rules, let statement s have immediate predecessor statements p1,...,pn
Rule
1. if C(pi, x, out) = T, for any i, then C(s, x, in) = T
2. if C(pi, x, out) = c & C(pj, x, out) = d & d <> c then C(s, x, in) = T
3. if C(pi, x, out) = c or $\perp$ for all i, then C(s, x, in) = c
4. if C(pi, x, out) = $\perp$ for all i, then C(s, x, in) = $\perp$
5. C(s, x, out) = $\perp$ if C(s, x, in) = $\perp$
6. C(x := c, x, out) = c if c is a constant
7. C(x := f(...), x, out) = T
8. C(y := ..., x, out) = C(y := ..., x, in) if x <> y
Algo
1. For every entry s to the program, set C(s, x, in) = T
2. Set C(s, x, in) = C(s, x, out) = $\perp$ everywhere else
3. Repeat until all points satisfy 1-8

We use $\perp$ to represent "So far as we know, control never reaches this point."
Initial
Because of cycles, all points must have values at all times
Intuitively, assigning some initial value allows the analysis to break cycles

Introduction

Orders of the values: $\perp$ < c < T
Drawing a picture with lower values drawn lower, we get
T is the greatest value, $\perp$ is the least
- All constants are in between and incomparable
Let lub be the least-upper bound in this ordering
- Rules 1-4 can be written using lub: C(s, x, in) = lub { C(p, x, out) | p is a predecessor of s }
The use of lub explains why the algorithm terminates
- Values start as $\perp$ and only increase
- $\perp$ can change to a constant, and a constant to T
- Thus, C(s, x, in/out) can change at most twice

Introduction

After constant propagation, we will eliminate dead code.
- The first value of x is dead (never used)
- The second value of x is live (may be used)
- Liveness is an important concept

Liveness

A variable x is live at statement s if
- There exists a statement s’ that uses x
- There is a path from s to s’
- That path has no intervening assignment to x
A statement x = ... is dead code if x is dead after the assignment
- Dead statements can be deleted from the program

How do we evaluate the liveness

Liveness is simpler than constant propagation, since it is a boolean property (true or false)
Rule
1. L(p, x, out) = $\lor$ { L(s, x, in) | s is a successor of p }
2. L(s, x, in) = true if s refers to x on the rhs
3. L(x := e, x, in) = false if e does not refer to x
4. L(s, x, in) = L(s, x, out) if s does not refer to x
Algo
1. Let all L(...) = false initially
2. Repeat until all statements s satisfy rules 1-4
  - Pick s where one of 1-4 does not hold and update using the appropriate rule
A value can change from false to true, but not the other way around
Each value can change only once, so termination is guaranteed
Once the analysis is computed, it is simple to eliminate dead code

Summary

Two kinds of analysis:
- Constant propagation is a forwards analysis: information is pushed from inputs to outputs
- Liveness is a backwards analysis: information is pushed from outputs back towards inputs
There are many other global flow analyses
Most can be classified as either forward or backward
Most also follow the methodology of local rules relating information between adjacent program points